package 力扣._207_课程表;

import java.util.*;

public class Solution {


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //拓扑排序
        //这个map相当于 正 邻接表了，得先找到入度为0的顶点
        int[] indegree = new int[numCourses];   //入度
        int count = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            List<Integer> list = map.getOrDefault(prerequisite[1], new LinkedList<>());
            list.add(prerequisite[0]);
            map.put(prerequisite[1], list);
            indegree[prerequisite[0]]++;
        }
        Stack<Integer> stack = new Stack<>();  //存储入度为0的顶点
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0)
                stack.push(i);
        }
        while (!stack.isEmpty()) {
            int pop = stack.pop();
            count++;
            //该顶点的邻接点的入度减一
            List<Integer> list = map.get(pop);
            if (list == null)
                continue;
            for (Integer node : list) {
                indegree[node]--;
                if (indegree[node] == 0)
                    stack.push(node);
            }
        }
        return count == numCourses;

    }
}
